package com.leetcode.BinaryTree;

//将有序数组转化为二叉搜索树
public class lc_108 {
    public static void main(String[] args) {

    }

    //给你一个整数数组nums,其中元素已经按升序排列,请你将其转换为一棵平衡二叉搜索树。
    public TreeNode sortedArrayToBST(int[] nums) {
        //1.判断:不需要维护全局变量,但是上层要给下层传入子数组范围,下层要给上层返回构建好的子二叉搜索树
        return helper(nums, 0, nums.length - 1);
    }

    //2.传入参数:nums数组,本棵子树所用到的子数组的左边界和有边界
    private TreeNode helper(int[] nums, int left, int right) {
        //3.边界条件,当传入left > right时说明最下层的子树已经构造完毕 返回此时的子树null
        if (left > right) {
            return null;
        }

        //4.每一层逻辑:
        //计算出中点,中点为本层树的根结点
        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        //继续递归得到左右平衡子树,根据方法写入传入参数
        root.left = helper(nums, left, mid - 1);
        root.right = helper(nums, mid + 1, right);
        //底层给上层返回已经构建好的平衡二叉搜索子树的头节点
        return root;
    }
}
